import java.util.ArrayList;
import java.util.List;

import javafx.util.Pair;

public class Solution3 {
    public int widthOfBinaryTree(TreeNode root) {
        List<Pair<TreeNode,Integer>> q = new ArrayList<>(); // 用数组模拟队列
        q.add(new Pair<TreeNode,Integer>(root,1));
        int ret = 0; // 记录最终结果

        while(!q.isEmpty()) {
            // 先更新这层的宽度
            Pair<TreeNode,Integer> t1 = q.get(0);
            Pair<TreeNode,Integer> t2 = q.get(q.size() - 1);
            ret = Math.max(t2.getValue() - t1.getValue() + 1, ret);

            // 让下一层进队
            List<Pair<TreeNode,Integer>> tmp = new ArrayList<>();
            for(Pair<TreeNode,Integer> t : q) {
                TreeNode node = t.getKey();
                int index = t.getValue();
                if(node.left != null) {
                    tmp.add(new Pair<TreeNode,Integer>(node.left, index * 2));
                }
                if(node.right != null) {
                    tmp.add(new Pair<TreeNode,Integer>(node.right, index * 2 + 1));
                }
            }
            q = tmp;
        }
        return ret;
    }
}
